home *** CD-ROM | disk | FTP | other *** search
/ Skunkware 98 / Skunkware 98.iso / src / mail / db.1.85.tar.gz / db.1.85.tar / db.1.85 / hash / hash.c < prev    next >
C/C++ Source or Header  |  1994-06-24  |  24KB  |  995 lines
  1. /*-
  2.  * Copyright (c) 1990, 1993, 1994
  3.  *    The Regents of the University of California.  All rights reserved.
  4.  *
  5.  * This code is derived from software contributed to Berkeley by
  6.  * Margo Seltzer.
  7.  *
  8.  * Redistribution and use in source and binary forms, with or without
  9.  * modification, are permitted provided that the following conditions
  10.  * are met:
  11.  * 1. Redistributions of source code must retain the above copyright
  12.  *    notice, this list of conditions and the following disclaimer.
  13.  * 2. Redistributions in binary form must reproduce the above copyright
  14.  *    notice, this list of conditions and the following disclaimer in the
  15.  *    documentation and/or other materials provided with the distribution.
  16.  * 3. All advertising materials mentioning features or use of this software
  17.  *    must display the following acknowledgement:
  18.  *    This product includes software developed by the University of
  19.  *    California, Berkeley and its contributors.
  20.  * 4. Neither the name of the University nor the names of its contributors
  21.  *    may be used to endorse or promote products derived from this software
  22.  *    without specific prior written permission.
  23.  *
  24.  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  25.  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  26.  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  27.  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  28.  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  29.  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  30.  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  31.  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  32.  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  33.  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  34.  * SUCH DAMAGE.
  35.  */
  36.  
  37. #if defined(LIBC_SCCS) && !defined(lint)
  38. static char sccsid[] = "@(#)hash.c    8.9 (Berkeley) 6/16/94";
  39. #endif /* LIBC_SCCS and not lint */
  40.  
  41. #include <sys/param.h>
  42. #include <sys/stat.h>
  43.  
  44. #include <errno.h>
  45. #include <fcntl.h>
  46. #include <stdio.h>
  47. #include <stdlib.h>
  48. #include <string.h>
  49. #include <unistd.h>
  50. #ifdef DEBUG
  51. #include <assert.h>
  52. #endif
  53.  
  54. #include <db.h>
  55. #include "hash.h"
  56. #include "page.h"
  57. #include "extern.h"
  58.  
  59. static int   alloc_segs __P((HTAB *, int));
  60. static int   flush_meta __P((HTAB *));
  61. static int   hash_access __P((HTAB *, ACTION, DBT *, DBT *));
  62. static int   hash_close __P((DB *));
  63. static int   hash_delete __P((const DB *, const DBT *, u_int32_t));
  64. static int   hash_fd __P((const DB *));
  65. static int   hash_get __P((const DB *, const DBT *, DBT *, u_int32_t));
  66. static int   hash_put __P((const DB *, DBT *, const DBT *, u_int32_t));
  67. static void *hash_realloc __P((SEGMENT **, int, int));
  68. static int   hash_seq __P((const DB *, DBT *, DBT *, u_int32_t));
  69. static int   hash_sync __P((const DB *, u_int32_t));
  70. static int   hdestroy __P((HTAB *));
  71. static HTAB *init_hash __P((HTAB *, const char *, HASHINFO *));
  72. static int   init_htab __P((HTAB *, int));
  73. #if BYTE_ORDER == LITTLE_ENDIAN
  74. static void  swap_header __P((HTAB *));
  75. static void  swap_header_copy __P((HASHHDR *, HASHHDR *));
  76. #endif
  77.  
  78. /* Fast arithmetic, relying on powers of 2, */
  79. #define MOD(x, y)        ((x) & ((y) - 1))
  80.  
  81. #define RETURN_ERROR(ERR, LOC)    { save_errno = ERR; goto LOC; }
  82.  
  83. /* Return values */
  84. #define    SUCCESS     (0)
  85. #define    ERROR    (-1)
  86. #define    ABNORMAL (1)
  87.  
  88. #ifdef HASH_STATISTICS
  89. int hash_accesses, hash_collisions, hash_expansions, hash_overflows;
  90. #endif
  91.  
  92. /************************** INTERFACE ROUTINES ***************************/
  93. /* OPEN/CLOSE */
  94.  
  95. extern DB *
  96. __hash_open(file, flags, mode, info, dflags)
  97.     const char *file;
  98.     int flags, mode, dflags;
  99.     const HASHINFO *info;    /* Special directives for create */
  100. {
  101.     HTAB *hashp;
  102.     struct stat statbuf;
  103.     DB *dbp;
  104.     int bpages, hdrsize, new_table, nsegs, save_errno;
  105.  
  106.     if ((flags & O_ACCMODE) == O_WRONLY) {
  107.         errno = EINVAL;
  108.         return (NULL);
  109.     }
  110.  
  111.     if (!(hashp = (HTAB *)calloc(1, sizeof(HTAB))))
  112.         return (NULL);
  113.     hashp->fp = -1;
  114.  
  115.     /*
  116.      * Even if user wants write only, we need to be able to read
  117.      * the actual file, so we need to open it read/write. But, the
  118.      * field in the hashp structure needs to be accurate so that
  119.      * we can check accesses.
  120.      */
  121.     hashp->flags = flags;
  122.  
  123.     new_table = 0;
  124.     if (!file || (flags & O_TRUNC) ||
  125.         (stat(file, &statbuf) && (errno == ENOENT))) {
  126.         if (errno == ENOENT)
  127.             errno = 0; /* Just in case someone looks at errno */
  128.         new_table = 1;
  129.     }
  130.     if (file) {
  131.         if ((hashp->fp = open(file, flags, mode)) == -1)
  132.             RETURN_ERROR(errno, error0);
  133.         (void)fcntl(hashp->fp, F_SETFD, 1);
  134.     }
  135.     if (new_table) {
  136.         if (!(hashp = init_hash(hashp, file, (HASHINFO *)info)))
  137.             RETURN_ERROR(errno, error1);
  138.     } else {
  139.         /* Table already exists */
  140.         if (info && info->hash)
  141.             hashp->hash = info->hash;
  142.         else
  143.             hashp->hash = __default_hash;
  144.  
  145.         hdrsize = read(hashp->fp, &hashp->hdr, sizeof(HASHHDR));
  146. #if BYTE_ORDER == LITTLE_ENDIAN
  147.         swap_header(hashp);
  148. #endif
  149.         if (hdrsize == -1)
  150.             RETURN_ERROR(errno, error1);
  151.         if (hdrsize != sizeof(HASHHDR))
  152.             RETURN_ERROR(EFTYPE, error1);
  153.         /* Verify file type, versions and hash function */
  154.         if (hashp->MAGIC != HASHMAGIC)
  155.             RETURN_ERROR(EFTYPE, error1);
  156. #define    OLDHASHVERSION    1
  157.         if (hashp->VERSION != HASHVERSION &&
  158.             hashp->VERSION != OLDHASHVERSION)
  159.             RETURN_ERROR(EFTYPE, error1);
  160.         if (hashp->hash(CHARKEY, sizeof(CHARKEY)) != hashp->H_CHARKEY)
  161.             RETURN_ERROR(EFTYPE, error1);
  162.         /*
  163.          * Figure out how many segments we need.  Max_Bucket is the
  164.          * maximum bucket number, so the number of buckets is
  165.          * max_bucket + 1.
  166.          */
  167.         nsegs = (hashp->MAX_BUCKET + 1 + hashp->SGSIZE - 1) /
  168.              hashp->SGSIZE;
  169.         hashp->nsegs = 0;
  170.         if (alloc_segs(hashp, nsegs))
  171.             /*
  172.              * If alloc_segs fails, table will have been destroyed
  173.              * and errno will have been set.
  174.              */
  175.             return (NULL);
  176.         /* Read in bitmaps */
  177.         bpages = (hashp->SPARES[hashp->OVFL_POINT] +
  178.             (hashp->BSIZE << BYTE_SHIFT) - 1) >>
  179.             (hashp->BSHIFT + BYTE_SHIFT);
  180.  
  181.         hashp->nmaps = bpages;
  182.         (void)memset(&hashp->mapp[0], 0, bpages * sizeof(u_int32_t *));
  183.     }
  184.  
  185.     /* Initialize Buffer Manager */
  186.     if (info && info->cachesize)
  187.         __buf_init(hashp, info->cachesize);
  188.     else
  189.         __buf_init(hashp, DEF_BUFSIZE);
  190.  
  191.     hashp->new_file = new_table;
  192.     hashp->save_file = file && (hashp->flags & O_RDWR);
  193.     hashp->cbucket = -1;
  194.     if (!(dbp = (DB *)malloc(sizeof(DB)))) {
  195.         save_errno = errno;
  196.         hdestroy(hashp);
  197.         errno = save_errno;
  198.         return (NULL);
  199.     }
  200.     dbp->internal = hashp;
  201.     dbp->close = hash_close;
  202.     dbp->del = hash_delete;
  203.     dbp->fd = hash_fd;
  204.     dbp->get = hash_get;
  205.     dbp->put = hash_put;
  206.     dbp->seq = hash_seq;
  207.     dbp->sync = hash_sync;
  208.     dbp->type = DB_HASH;
  209.  
  210. #ifdef DEBUG
  211.     (void)fprintf(stderr,
  212. "%s\n%s%x\n%s%d\n%s%d\n%s%d\n%s%d\n%s%d\n%s%d\n%s%d\n%s%d\n%s%d\n%s%x\n%s%x\n%s%d\n%s%d\n",
  213.         "init_htab:",
  214.         "TABLE POINTER   ", hashp,
  215.         "BUCKET SIZE     ", hashp->BSIZE,
  216.         "BUCKET SHIFT    ", hashp->BSHIFT,
  217.         "DIRECTORY SIZE  ", hashp->DSIZE,
  218.         "SEGMENT SIZE    ", hashp->SGSIZE,
  219.         "SEGMENT SHIFT   ", hashp->SSHIFT,
  220.         "FILL FACTOR     ", hashp->FFACTOR,
  221.         "MAX BUCKET      ", hashp->MAX_BUCKET,
  222.         "OVFL POINT         ", hashp->OVFL_POINT,
  223.         "LAST FREED      ", hashp->LAST_FREED,
  224.         "HIGH MASK       ", hashp->HIGH_MASK,
  225.         "LOW  MASK       ", hashp->LOW_MASK,
  226.         "NSEGS           ", hashp->nsegs,
  227.         "NKEYS           ", hashp->NKEYS);
  228. #endif
  229. #ifdef HASH_STATISTICS
  230.     hash_overflows = hash_accesses = hash_collisions = hash_expansions = 0;
  231. #endif
  232.     return (dbp);
  233.  
  234. error1:
  235.     if (hashp != NULL)
  236.         (void)close(hashp->fp);
  237.  
  238. error0:
  239.     free(hashp);
  240.     errno = save_errno;
  241.     return (NULL);
  242. }
  243.  
  244. static int
  245. hash_close(dbp)
  246.     DB *dbp;
  247. {
  248.     HTAB *hashp;
  249.     int retval;
  250.  
  251.     if (!dbp)
  252.         return (ERROR);
  253.  
  254.     hashp = (HTAB *)dbp->internal;
  255.     retval = hdestroy(hashp);
  256.     free(dbp);
  257.     return (retval);
  258. }
  259.  
  260. static int
  261. hash_fd(dbp)
  262.     const DB *dbp;
  263. {
  264.     HTAB *hashp;
  265.  
  266.     if (!dbp)
  267.         return (ERROR);
  268.  
  269.     hashp = (HTAB *)dbp->internal;
  270.     if (hashp->fp == -1) {
  271.         errno = ENOENT;
  272.         return (-1);
  273.     }
  274.     return (hashp->fp);
  275. }
  276.  
  277. /************************** LOCAL CREATION ROUTINES **********************/
  278. static HTAB *
  279. init_hash(hashp, file, info)
  280.     HTAB *hashp;
  281.     const char *file;
  282.     HASHINFO *info;
  283. {
  284.     struct stat statbuf;
  285.     int nelem;
  286.  
  287.     nelem = 1;
  288.     hashp->NKEYS = 0;
  289.     hashp->LORDER = BYTE_ORDER;
  290.     hashp->BSIZE = DEF_BUCKET_SIZE;
  291.     hashp->BSHIFT = DEF_BUCKET_SHIFT;
  292.     hashp->SGSIZE = DEF_SEGSIZE;
  293.     hashp->SSHIFT = DEF_SEGSIZE_SHIFT;
  294.     hashp->DSIZE = DEF_DIRSIZE;
  295.     hashp->FFACTOR = DEF_FFACTOR;
  296.     hashp->hash = __default_hash;
  297.     memset(hashp->SPARES, 0, sizeof(hashp->SPARES));
  298.     memset(hashp->BITMAPS, 0, sizeof (hashp->BITMAPS));
  299.  
  300.     /* Fix bucket size to be optimal for file system */
  301.     if (file != NULL) {
  302.         if (stat(file, &statbuf))
  303.             return (NULL);
  304.         hashp->BSIZE = statbuf.st_blksize;
  305.         hashp->BSHIFT = __log2(hashp->BSIZE);
  306.     }
  307.  
  308.     if (info) {
  309.         if (info->bsize) {
  310.             /* Round pagesize up to power of 2 */
  311.             hashp->BSHIFT = __log2(info->bsize);
  312.             hashp->BSIZE = 1 << hashp->BSHIFT;
  313.             if (hashp->BSIZE > MAX_BSIZE) {
  314.                 errno = EINVAL;
  315.                 return (NULL);
  316.             }
  317.         }
  318.         if (info->ffactor)
  319.             hashp->FFACTOR = info->ffactor;
  320.         if (info->hash)
  321.             hashp->hash = info->hash;
  322.         if (info->nelem)
  323.             nelem = info->nelem;
  324.         if (info->lorder) {
  325.             if (info->lorder != BIG_ENDIAN &&
  326.                 info->lorder != LITTLE_ENDIAN) {
  327.                 errno = EINVAL;
  328.                 return (NULL);
  329.             }
  330.             hashp->LORDER = info->lorder;
  331.         }
  332.     }
  333.     /* init_htab should destroy the table and set errno if it fails */
  334.     if (init_htab(hashp, nelem))
  335.         return (NULL);
  336.     else
  337.         return (hashp);
  338. }
  339. /*
  340.  * This calls alloc_segs which may run out of memory.  Alloc_segs will destroy
  341.  * the table and set errno, so we just pass the error information along.
  342.  *
  343.  * Returns 0 on No Error
  344.  */
  345. static int
  346. init_htab(hashp, nelem)
  347.     HTAB *hashp;
  348.     int nelem;
  349. {
  350.     register int nbuckets, nsegs;
  351.     int l2;
  352.  
  353.     /*
  354.      * Divide number of elements by the fill factor and determine a
  355.      * desired number of buckets.  Allocate space for the next greater
  356.      * power of two number of buckets.
  357.      */
  358.     nelem = (nelem - 1) / hashp->FFACTOR + 1;
  359.  
  360.     l2 = __log2(MAX(nelem, 2));
  361.     nbuckets = 1 << l2;
  362.  
  363.     hashp->SPARES[l2] = l2 + 1;
  364.     hashp->SPARES[l2 + 1] = l2 + 1;
  365.     hashp->OVFL_POINT = l2;
  366.     hashp->LAST_FREED = 2;
  367.  
  368.     /* First bitmap page is at: splitpoint l2 page offset 1 */
  369.     if (__ibitmap(hashp, OADDR_OF(l2, 1), l2 + 1, 0))
  370.         return (-1);
  371.  
  372.     hashp->MAX_BUCKET = hashp->LOW_MASK = nbuckets - 1;
  373.     hashp->HIGH_MASK = (nbuckets << 1) - 1;
  374.     hashp->HDRPAGES = ((MAX(sizeof(HASHHDR), MINHDRSIZE) - 1) >>
  375.         hashp->BSHIFT) + 1;
  376.  
  377.     nsegs = (nbuckets - 1) / hashp->SGSIZE + 1;
  378.     nsegs = 1 << __log2(nsegs);
  379.  
  380.     if (nsegs > hashp->DSIZE)
  381.         hashp->DSIZE = nsegs;
  382.     return (alloc_segs(hashp, nsegs));
  383. }
  384.  
  385. /********************** DESTROY/CLOSE ROUTINES ************************/
  386.  
  387. /*
  388.  * Flushes any changes to the file if necessary and destroys the hashp
  389.  * structure, freeing all allocated space.
  390.  */
  391. static int
  392. hdestroy(hashp)
  393.     HTAB *hashp;
  394. {
  395.     int i, save_errno;
  396.  
  397.     save_errno = 0;
  398.  
  399. #ifdef HASH_STATISTICS
  400.     (void)fprintf(stderr, "hdestroy: accesses %ld collisions %ld\n",
  401.         hash_accesses, hash_collisions);
  402.     (void)fprintf(stderr, "hdestroy: expansions %ld\n",
  403.         hash_expansions);
  404.     (void)fprintf(stderr, "hdestroy: overflows %ld\n",
  405.         hash_overflows);
  406.     (void)fprintf(stderr, "keys %ld maxp %d segmentcount %d\n",
  407.         hashp->NKEYS, hashp->MAX_BUCKET, hashp->nsegs);
  408.  
  409.     for (i = 0; i < NCACHED; i++)
  410.         (void)fprintf(stderr,
  411.             "spares[%d] = %d\n", i, hashp->SPARES[i]);
  412. #endif
  413.     /*
  414.      * Call on buffer manager to free buffers, and if required,
  415.      * write them to disk.
  416.      */
  417.     if (__buf_free(hashp, 1, hashp->save_file))
  418.         save_errno = errno;
  419.     if (hashp->dir) {
  420.         free(*hashp->dir);    /* Free initial segments */
  421.         /* Free extra segments */
  422.         while (hashp->exsegs--)
  423.             free(hashp->dir[--hashp->nsegs]);
  424.         free(hashp->dir);
  425.     }
  426.     if (flush_meta(hashp) && !save_errno)
  427.         save_errno = errno;
  428.     /* Free Bigmaps */
  429.     for (i = 0; i < hashp->nmaps; i++)
  430.         if (hashp->mapp[i])
  431.             free(hashp->mapp[i]);
  432.  
  433.     if (hashp->fp != -1)
  434.         (void)close(hashp->fp);
  435.  
  436.     free(hashp);
  437.  
  438.     if (save_errno) {
  439.         errno = save_errno;
  440.         return (ERROR);
  441.     }
  442.     return (SUCCESS);
  443. }
  444. /*
  445.  * Write modified pages to disk
  446.  *
  447.  * Returns:
  448.  *     0 == OK
  449.  *    -1 ERROR
  450.  */
  451. static int
  452. hash_sync(dbp, flags)
  453.     const DB *dbp;
  454.     u_int32_t flags;
  455. {
  456.     HTAB *hashp;
  457.  
  458.     if (flags != 0) {
  459.         errno = EINVAL;
  460.         return (ERROR);
  461.     }
  462.  
  463.     if (!dbp)
  464.         return (ERROR);
  465.  
  466.     hashp = (HTAB *)dbp->internal;
  467.     if (!hashp->save_file)
  468.         return (0);
  469.     if (__buf_free(hashp, 0, 1) || flush_meta(hashp))
  470.         return (ERROR);
  471.     hashp->new_file = 0;
  472.     return (0);
  473. }
  474.  
  475. /*
  476.  * Returns:
  477.  *     0 == OK
  478.  *    -1 indicates that errno should be set
  479.  */
  480. static int
  481. flush_meta(hashp)
  482.     HTAB *hashp;
  483. {
  484.     HASHHDR *whdrp;
  485. #if BYTE_ORDER == LITTLE_ENDIAN
  486.     HASHHDR whdr;
  487. #endif
  488.     int fp, i, wsize;
  489.  
  490.     if (!hashp->save_file)
  491.         return (0);
  492.     hashp->MAGIC = HASHMAGIC;
  493.     hashp->VERSION = HASHVERSION;
  494.     hashp->H_CHARKEY = hashp->hash(CHARKEY, sizeof(CHARKEY));
  495.  
  496.     fp = hashp->fp;
  497.     whdrp = &hashp->hdr;
  498. #if BYTE_ORDER == LITTLE_ENDIAN
  499.     whdrp = &whdr;
  500.     swap_header_copy(&hashp->hdr, whdrp);
  501. #endif
  502.     if ((lseek(fp, (off_t)0, SEEK_SET) == -1) ||
  503.         ((wsize = write(fp, whdrp, sizeof(HASHHDR))) == -1))
  504.         return (-1);
  505.     else
  506.         if (wsize != sizeof(HASHHDR)) {
  507.             errno = EFTYPE;
  508.             hashp->errno = errno;
  509.             return (-1);
  510.         }
  511.     for (i = 0; i < NCACHED; i++)
  512.         if (hashp->mapp[i])
  513.             if (__put_page(hashp, (char *)hashp->mapp[i],
  514.                 hashp->BITMAPS[i], 0, 1))
  515.                 return (-1);
  516.     return (0);
  517. }
  518.  
  519. /*******************************SEARCH ROUTINES *****************************/
  520. /*
  521.  * All the access routines return
  522.  *
  523.  * Returns:
  524.  *     0 on SUCCESS
  525.  *     1 to indicate an external ERROR (i.e. key not found, etc)
  526.  *    -1 to indicate an internal ERROR (i.e. out of memory, etc)
  527.  */
  528. static int
  529. hash_get(dbp, key, data, flag)
  530.     const DB *dbp;
  531.     const DBT *key;
  532.     DBT *data;
  533.     u_int32_t flag;
  534. {
  535.     HTAB *hashp;
  536.  
  537.     hashp = (HTAB *)dbp->internal;
  538.     if (flag) {
  539.         hashp->errno = errno = EINVAL;
  540.         return (ERROR);
  541.     }
  542.     return (hash_access(hashp, HASH_GET, (DBT *)key, data));
  543. }
  544.  
  545. static int
  546. hash_put(dbp, key, data, flag)
  547.     const DB *dbp;
  548.     DBT *key;
  549.     const DBT *data;
  550.     u_int32_t flag;
  551. {
  552.     HTAB *hashp;
  553.  
  554.     hashp = (HTAB *)dbp->internal;
  555.     if (flag && flag != R_NOOVERWRITE) {
  556.         hashp->errno = errno = EINVAL;
  557.         return (ERROR);
  558.     }
  559.     if ((hashp->flags & O_ACCMODE) == O_RDONLY) {
  560.         hashp->errno = errno = EPERM;
  561.         return (ERROR);
  562.     }
  563.     return (hash_access(hashp, flag == R_NOOVERWRITE ?
  564.         HASH_PUTNEW : HASH_PUT, (DBT *)key, (DBT *)data));
  565. }
  566.  
  567. static int
  568. hash_delete(dbp, key, flag)
  569.     const DB *dbp;
  570.     const DBT *key;
  571.     u_int32_t flag;        /* Ignored */
  572. {
  573.     HTAB *hashp;
  574.  
  575.     hashp = (HTAB *)dbp->internal;
  576.     if (flag && flag != R_CURSOR) {
  577.         hashp->errno = errno = EINVAL;
  578.         return (ERROR);
  579.     }
  580.     if ((hashp->flags & O_ACCMODE) == O_RDONLY) {
  581.         hashp->errno = errno = EPERM;
  582.         return (ERROR);
  583.     }
  584.     return (hash_access(hashp, HASH_DELETE, (DBT *)key, NULL));
  585. }
  586.  
  587. /*
  588.  * Assume that hashp has been set in wrapper routine.
  589.  */
  590. static int
  591. hash_access(hashp, action, key, val)
  592.     HTAB *hashp;
  593.     ACTION action;
  594.     DBT *key, *val;
  595. {
  596.     register BUFHEAD *rbufp;
  597.     BUFHEAD *bufp, *save_bufp;
  598.     register u_int16_t *bp;
  599.     register int n, ndx, off, size;
  600.     register char *kp;
  601.     u_int16_t pageno;
  602.  
  603. #ifdef HASH_STATISTICS
  604.     hash_accesses++;
  605. #endif
  606.  
  607.     off = hashp->BSIZE;
  608.     size = key->size;
  609.     kp = (char *)key->data;
  610.     rbufp = __get_buf(hashp, __call_hash(hashp, kp, size), NULL, 0);
  611.     if (!rbufp)
  612.         return (ERROR);
  613.     save_bufp = rbufp;
  614.  
  615.     /* Pin the bucket chain */
  616.     rbufp->flags |= BUF_PIN;
  617.     for (bp = (u_int16_t *)rbufp->page, n = *bp++, ndx = 1; ndx < n;)
  618.         if (bp[1] >= REAL_KEY) {
  619.             /* Real key/data pair */
  620.             if (size == off - *bp &&
  621.                 memcmp(kp, rbufp->page + *bp, size) == 0)
  622.                 goto found;
  623.             off = bp[1];
  624. #ifdef HASH_STATISTICS
  625.             hash_collisions++;
  626. #endif
  627.             bp += 2;
  628.             ndx += 2;
  629.         } else if (bp[1] == OVFLPAGE) {
  630.             rbufp = __get_buf(hashp, *bp, rbufp, 0);
  631.             if (!rbufp) {
  632.                 save_bufp->flags &= ~BUF_PIN;
  633.                 return (ERROR);
  634.             }
  635.             /* FOR LOOP INIT */
  636.             bp = (u_int16_t *)rbufp->page;
  637.             n = *bp++;
  638.             ndx = 1;
  639.             off = hashp->BSIZE;
  640.         } else if (bp[1] < REAL_KEY) {
  641.             if ((ndx =
  642.                 __find_bigpair(hashp, rbufp, ndx, kp, size)) > 0)
  643.                 goto found;
  644.             if (ndx == -2) {
  645.                 bufp = rbufp;
  646.                 if (!(pageno =
  647.                     __find_last_page(hashp, &bufp))) {
  648.                     ndx = 0;
  649.                     rbufp = bufp;
  650.                     break;    /* FOR */
  651.                 }
  652.                 rbufp = __get_buf(hashp, pageno, bufp, 0);
  653.                 if (!rbufp) {
  654.                     save_bufp->flags &= ~BUF_PIN;
  655.                     return (ERROR);
  656.                 }
  657.                 /* FOR LOOP INIT */
  658.                 bp = (u_int16_t *)rbufp->page;
  659.                 n = *bp++;
  660.                 ndx = 1;
  661.                 off = hashp->BSIZE;
  662.             } else {
  663.                 save_bufp->flags &= ~BUF_PIN;
  664.                 return (ERROR);
  665.             }
  666.         }
  667.  
  668.     /* Not found */
  669.     switch (action) {
  670.     case HASH_PUT:
  671.     case HASH_PUTNEW:
  672.         if (__addel(hashp, rbufp, key, val)) {
  673.             save_bufp->flags &= ~BUF_PIN;
  674.             return (ERROR);
  675.         } else {
  676.             save_bufp->flags &= ~BUF_PIN;
  677.             return (SUCCESS);
  678.         }
  679.     case HASH_GET:
  680.     case HASH_DELETE:
  681.     default:
  682.         save_bufp->flags &= ~BUF_PIN;
  683.         return (ABNORMAL);
  684.     }
  685.  
  686. found:
  687.     switch (action) {
  688.     case HASH_PUTNEW:
  689.         save_bufp->flags &= ~BUF_PIN;
  690.         return (ABNORMAL);
  691.     case HASH_GET:
  692.         bp = (u_int16_t *)rbufp->page;
  693.         if (bp[ndx + 1] < REAL_KEY) {
  694.             if (__big_return(hashp, rbufp, ndx, val, 0))
  695.                 return (ERROR);
  696.         } else {
  697.             val->data = (u_char *)rbufp->page + (int)bp[ndx + 1];
  698.             val->size = bp[ndx] - bp[ndx + 1];
  699.         }
  700.         break;
  701.     case HASH_PUT:
  702.         if ((__delpair(hashp, rbufp, ndx)) ||
  703.             (__addel(hashp, rbufp, key, val))) {
  704.             save_bufp->flags &= ~BUF_PIN;
  705.             return (ERROR);
  706.         }
  707.         break;
  708.     case HASH_DELETE:
  709.         if (__delpair(hashp, rbufp, ndx))
  710.             return (ERROR);
  711.         break;
  712.     default:
  713.         abort();
  714.     }
  715.     save_bufp->flags &= ~BUF_PIN;
  716.     return (SUCCESS);
  717. }
  718.  
  719. static int
  720. hash_seq(dbp, key, data, flag)
  721.     const DB *dbp;
  722.     DBT *key, *data;
  723.     u_int32_t flag;
  724. {
  725.     register u_int32_t bucket;
  726.     register BUFHEAD *bufp;
  727.     HTAB *hashp;
  728.     u_int16_t *bp, ndx;
  729.  
  730.     hashp = (HTAB *)dbp->internal;
  731.     if (flag && flag != R_FIRST && flag != R_NEXT) {
  732.         hashp->errno = errno = EINVAL;
  733.         return (ERROR);
  734.     }
  735. #ifdef HASH_STATISTICS
  736.     hash_accesses++;
  737. #endif
  738.     if ((hashp->cbucket < 0) || (flag == R_FIRST)) {
  739.         hashp->cbucket = 0;
  740.         hashp->cndx = 1;
  741.         hashp->cpage = NULL;
  742.     }
  743.  
  744.     for (bp = NULL; !bp || !bp[0]; ) {
  745.         if (!(bufp = hashp->cpage)) {
  746.             for (bucket = hashp->cbucket;
  747.                 bucket <= hashp->MAX_BUCKET;
  748.                 bucket++, hashp->cndx = 1) {
  749.                 bufp = __get_buf(hashp, bucket, NULL, 0);
  750.                 if (!bufp)
  751.                     return (ERROR);
  752.                 hashp->cpage = bufp;
  753.                 bp = (u_int16_t *)bufp->page;
  754.                 if (bp[0])
  755.                     break;
  756.             }
  757.             hashp->cbucket = bucket;
  758.             if (hashp->cbucket > hashp->MAX_BUCKET) {
  759.                 hashp->cbucket = -1;
  760.                 return (ABNORMAL);
  761.             }
  762.         } else
  763.             bp = (u_int16_t *)hashp->cpage->page;
  764.  
  765. #ifdef DEBUG
  766.         assert(bp);
  767.         assert(bufp);
  768. #endif
  769.         while (bp[hashp->cndx + 1] == OVFLPAGE) {
  770.             bufp = hashp->cpage =
  771.                 __get_buf(hashp, bp[hashp->cndx], bufp, 0);
  772.             if (!bufp)
  773.                 return (ERROR);
  774.             bp = (u_int16_t *)(bufp->page);
  775.             hashp->cndx = 1;
  776.         }
  777.         if (!bp[0]) {
  778.             hashp->cpage = NULL;
  779.             ++hashp->cbucket;
  780.         }
  781.     }
  782.     ndx = hashp->cndx;
  783.     if (bp[ndx + 1] < REAL_KEY) {
  784.         if (__big_keydata(hashp, bufp, key, data, 1))
  785.             return (ERROR);
  786.     } else {
  787.         key->data = (u_char *)hashp->cpage->page + bp[ndx];
  788.         key->size = (ndx > 1 ? bp[ndx - 1] : hashp->BSIZE) - bp[ndx];
  789.         data->data = (u_char *)hashp->cpage->page + bp[ndx + 1];
  790.         data->size = bp[ndx] - bp[ndx + 1];
  791.         ndx += 2;
  792.         if (ndx > bp[0]) {
  793.             hashp->cpage = NULL;
  794.             hashp->cbucket++;
  795.             hashp->cndx = 1;
  796.         } else
  797.             hashp->cndx = ndx;
  798.     }
  799.     return (SUCCESS);
  800. }
  801.  
  802. /********************************* UTILITIES ************************/
  803.  
  804. /*
  805.  * Returns:
  806.  *     0 ==> OK
  807.  *    -1 ==> Error
  808.  */
  809. extern int
  810. __expand_table(hashp)
  811.     HTAB *hashp;
  812. {
  813.     u_int32_t old_bucket, new_bucket;
  814.     int dirsize, new_segnum, spare_ndx;
  815.  
  816. #ifdef HASH_STATISTICS
  817.     hash_expansions++;
  818. #endif
  819.     new_bucket = ++hashp->MAX_BUCKET;
  820.     old_bucket = (hashp->MAX_BUCKET & hashp->LOW_MASK);
  821.  
  822.     new_segnum = new_bucket >> hashp->SSHIFT;
  823.  
  824.     /* Check if we need a new segment */
  825.     if (new_segnum >= hashp->nsegs) {
  826.         /* Check if we need to expand directory */
  827.         if (new_segnum >= hashp->DSIZE) {
  828.             /* Reallocate directory */
  829.             dirsize = hashp->DSIZE * sizeof(SEGMENT *);
  830.             if (!hash_realloc(&hashp->dir, dirsize, dirsize << 1))
  831.                 return (-1);
  832.             hashp->DSIZE = dirsize << 1;
  833.         }
  834.         if ((hashp->dir[new_segnum] =
  835.             (SEGMENT)calloc(hashp->SGSIZE, sizeof(SEGMENT))) == NULL)
  836.             return (-1);
  837.         hashp->exsegs++;
  838.         hashp->nsegs++;
  839.     }
  840.     /*
  841.      * If the split point is increasing (MAX_BUCKET's log base 2
  842.      * * increases), we need to copy the current contents of the spare
  843.      * split bucket to the next bucket.
  844.      */
  845.     spare_ndx = __log2(hashp->MAX_BUCKET + 1);
  846.     if (spare_ndx > hashp->OVFL_POINT) {
  847.         hashp->SPARES[spare_ndx] = hashp->SPARES[hashp->OVFL_POINT];
  848.         hashp->OVFL_POINT = spare_ndx;
  849.     }
  850.  
  851.     if (new_bucket > hashp->HIGH_MASK) {
  852.         /* Starting a new doubling */
  853.         hashp->LOW_MASK = hashp->HIGH_MASK;
  854.         hashp->HIGH_MASK = new_bucket | hashp->LOW_MASK;
  855.     }
  856.     /* Relocate records to the new bucket */
  857.     return (__split_page(hashp, old_bucket, new_bucket));
  858. }
  859.  
  860. /*
  861.  * If realloc guarantees that the pointer is not destroyed if the realloc
  862.  * fails, then this routine can go away.
  863.  */
  864. static void *
  865. hash_realloc(p_ptr, oldsize, newsize)
  866.     SEGMENT **p_ptr;
  867.     int oldsize, newsize;
  868. {
  869.     register void *p;
  870.  
  871.     if (p = malloc(newsize)) {
  872.         memmove(p, *p_ptr, oldsize);
  873.         memset((char *)p + oldsize, 0, newsize - oldsize);
  874.         free(*p_ptr);
  875.         *p_ptr = p;
  876.     }
  877.     return (p);
  878. }
  879.  
  880. extern u_int32_t
  881. __call_hash(hashp, k, len)
  882.     HTAB *hashp;
  883.     char *k;
  884.     int len;
  885. {
  886.     int n, bucket;
  887.  
  888.     n = hashp->hash(k, len);
  889.     bucket = n & hashp->HIGH_MASK;
  890.     if (bucket > hashp->MAX_BUCKET)
  891.         bucket = bucket & hashp->LOW_MASK;
  892.     return (bucket);
  893. }
  894.  
  895. /*
  896.  * Allocate segment table.  On error, destroy the table and set errno.
  897.  *
  898.  * Returns 0 on success
  899.  */
  900. static int
  901. alloc_segs(hashp, nsegs)
  902.     HTAB *hashp;
  903.     int nsegs;
  904. {
  905.     register int i;
  906.     register SEGMENT store;
  907.  
  908.     int save_errno;
  909.  
  910.     if ((hashp->dir =
  911.         (SEGMENT *)calloc(hashp->DSIZE, sizeof(SEGMENT *))) == NULL) {
  912.         save_errno = errno;
  913.         (void)hdestroy(hashp);
  914.         errno = save_errno;
  915.         return (-1);
  916.     }
  917.     /* Allocate segments */
  918.     if ((store =
  919.         (SEGMENT)calloc(nsegs << hashp->SSHIFT, sizeof(SEGMENT))) == NULL) {
  920.         save_errno = errno;
  921.         (void)hdestroy(hashp);
  922.         errno = save_errno;
  923.         return (-1);
  924.     }
  925.     for (i = 0; i < nsegs; i++, hashp->nsegs++)
  926.         hashp->dir[i] = &store[i << hashp->SSHIFT];
  927.     return (0);
  928. }
  929.  
  930. #if BYTE_ORDER == LITTLE_ENDIAN
  931. /*
  932.  * Hashp->hdr needs to be byteswapped.
  933.  */
  934. static void
  935. swap_header_copy(srcp, destp)
  936.     HASHHDR *srcp, *destp;
  937. {
  938.     int i;
  939.  
  940.     P_32_COPY(srcp->magic, destp->magic);
  941.     P_32_COPY(srcp->version, destp->version);
  942.     P_32_COPY(srcp->lorder, destp->lorder);
  943.     P_32_COPY(srcp->bsize, destp->bsize);
  944.     P_32_COPY(srcp->bshift, destp->bshift);
  945.     P_32_COPY(srcp->dsize, destp->dsize);
  946.     P_32_COPY(srcp->ssize, destp->ssize);
  947.     P_32_COPY(srcp->sshift, destp->sshift);
  948.     P_32_COPY(srcp->ovfl_point, destp->ovfl_point);
  949.     P_32_COPY(srcp->last_freed, destp->last_freed);
  950.     P_32_COPY(srcp->max_bucket, destp->max_bucket);
  951.     P_32_COPY(srcp->high_mask, destp->high_mask);
  952.     P_32_COPY(srcp->low_mask, destp->low_mask);
  953.     P_32_COPY(srcp->ffactor, destp->ffactor);
  954.     P_32_COPY(srcp->nkeys, destp->nkeys);
  955.     P_32_COPY(srcp->hdrpages, destp->hdrpages);
  956.     P_32_COPY(srcp->h_charkey, destp->h_charkey);
  957.     for (i = 0; i < NCACHED; i++) {
  958.         P_32_COPY(srcp->spares[i], destp->spares[i]);
  959.         P_16_COPY(srcp->bitmaps[i], destp->bitmaps[i]);
  960.     }
  961. }
  962.  
  963. static void
  964. swap_header(hashp)
  965.     HTAB *hashp;
  966. {
  967.     HASHHDR *hdrp;
  968.     int i;
  969.  
  970.     hdrp = &hashp->hdr;
  971.  
  972.     M_32_SWAP(hdrp->magic);
  973.     M_32_SWAP(hdrp->version);
  974.     M_32_SWAP(hdrp->lorder);
  975.     M_32_SWAP(hdrp->bsize);
  976.     M_32_SWAP(hdrp->bshift);
  977.     M_32_SWAP(hdrp->dsize);
  978.     M_32_SWAP(hdrp->ssize);
  979.     M_32_SWAP(hdrp->sshift);
  980.     M_32_SWAP(hdrp->ovfl_point);
  981.     M_32_SWAP(hdrp->last_freed);
  982.     M_32_SWAP(hdrp->max_bucket);
  983.     M_32_SWAP(hdrp->high_mask);
  984.     M_32_SWAP(hdrp->low_mask);
  985.     M_32_SWAP(hdrp->ffactor);
  986.     M_32_SWAP(hdrp->nkeys);
  987.     M_32_SWAP(hdrp->hdrpages);
  988.     M_32_SWAP(hdrp->h_charkey);
  989.     for (i = 0; i < NCACHED; i++) {
  990.         M_32_SWAP(hdrp->spares[i]);
  991.         M_16_SWAP(hdrp->bitmaps[i]);
  992.     }
  993. }
  994. #endif
  995.